package cn.mayday.algorithms.year2021.month1.C双指针专题;

/**
 * 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "We are happy."
 * 输出："We%20are%20happy."
 *
 *
 *
 * 限制：
 *
 * 0 <= s 的长度 <= 10000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author Mayday05
 * @date 2021/1/3 9:42
 */
public class Off05ReplaceSpace {

    public static void main(String[] args) {
        String input1 = "We are happy.";
        String result1 = new Off05ReplaceSpace().replaceSpace(input1);
        System.out.println("result1 = " + result1);

        String input2 = "    ";
        String result2 = new Off05ReplaceSpace().replaceSpace(input2);
        System.out.println("result2 = " + result2);
    }

    // 方法一： 暴力循环，时间复杂度O(n)，空间复杂度O(n)
    public String replaceSpace1(String s) {
        if (s == null) {
            return null;
        }
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char temp = s.charAt(i);
            if(temp == ' ') {
                builder.append("%20");
            } else {
                builder.append(temp);
            }
        }
        return builder.toString();
    }

    // 方法二： 双指针法 运用双指针的算法思想求解

    // 双指针的算法思想：设置两个指示位（指针），指向字符串的末尾，移动一个指针至空格所在位置，
    // 此时两个指针之间的子串不存在空格，是最终字符串的组成部分，通过在此段字串之前添加字符串“%20”，
    // 对整个字符串进行此操作，所得结果即为要求字符串。
    //
    // 时间复杂度：O(n) 空间复杂度：O(1)【没有再开辟一个空间重用原来空间，不对，其实还是O(N)】
    public String replaceSpace(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char temp = s.charAt(i);
            if (temp == ' ') {
                count++;
            }
        }
        int oldLength = s.length();
        int newLength = s.length() + count * 2; // 计算新的数组的大小

        char[] newS = new char[newLength];

        while (oldLength > 0 && newLength > 0) {
            char temp = s.charAt(oldLength - 1); // 遍历就数组元素

            if (temp == ' ') { // 如果为空格，分别赋值，并且新元素下标递减
                newS[newLength - 1] = '0';
                newS[newLength - 2] = '2';
                newS[newLength - 3] = '%';
                newLength = newLength - 3;
            } else {
                newS[newLength - 1] = temp;
                newLength--;
            }
            oldLength--;
        }
        return String.valueOf(newS);
    }
}
